package DataStructureAndAlgorithm.Acwing.DP.数字三角形DP;

/*
问题分析：是摘花生题目的扩展，不过摘花生是一个人摘，这里是两个人摘，因此仍然可以用摘花生的思路来思考
问题描述：求两个人都是nums[1][1]出发，到达终点时，两个人摘花生的总和最大是多少
状态描述：用dp[i1][i2][j1][j2]表示两个人分别到达[i1][j1]和[i2][j2]过程中说能摘到的最大花生的值
状态优化：
        由于状态方程dp[i1][i2][j1][j2]表示的两个人只有在经过相同步数的情况下，才有可能经过同一路径。
        因此，可以用k表示两个人经过的路径步数总和(可以规定两个都是同时走的，而且每次走一步)
状态表示：
        dp[k][i1][i2]：表示两个人同时走了k步，分别到到[i1][j1]和[i2][j2]时所能摘取的最大花生的数量
        (其中j1 = k - i1, j2 = k - i2)
状态方程：
        //两个数到达nums[i][j]的最后一步都是从上往下走
        dp[k][i1][i2] = Math.max(dp[k][i1][i2],dp[k - 1][i1 - 1][i2 - 1] + t);
        //两个数到达nums[i][j]的最后一步一个从上往下走，一个从左往右走
        dp[k][i1][i2] = Math.max(dp[k][i1][i2],dp[k - 1][i1 - 1][i2] + t);
        //两个数到达nums[i][j]的最后一步一个从左往右走，一个从上往下走
        dp[k][i1][i2] = Math.max(dp[k][i1][i2],dp[k - 1][i1][i2 - 1] + t);
        //两个数到达nums[i][j]的最后一步都是从左往右走
        dp[k][i1][i2] = Math.max(dp[k][i1][i2],dp[k - 1][i1][i2] + t);
*/


import java.util.*;

class dp_1027{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] nums = new int[n + 1][n + 1];
        int a,b,c;
        do{
            a = in.nextInt();
            b = in.nextInt();
            c = in.nextInt();
            nums[a][b] = c;
        }while(a != 0 && b != 0 && c != 0);
        int[][][] dp = new int[2 * (n + 1)][n + 1][n + 1];
        for (int k = 2; k <= 2 * n; k++){
            for (int i1 = 1; i1 <= n; i1++){
                for (int i2 = 1; i2 <= n; i2++){
                    int j1 = k - i1;
                    int j2 = k - i2;
                    if (j1 >= 1 && j2 >= 1 && j1 <= n && j2 <= n){
                        int t = nums[i1][j1];
                        //判断是否经过了同一点，不同的两个数都加上，否则只加一个
                        if (i1 != i2)t += nums[i2][j2];
                        //两个数到达nums[i][j]的最后一步都是从上往下走
                        dp[k][i1][i2] = Math.max(dp[k][i1][i2],dp[k - 1][i1 - 1][i2 - 1] + t);
                        //两个数到达nums[i][j]的最后一步一个从上往下走，一个从左往右走
                        dp[k][i1][i2] = Math.max(dp[k][i1][i2],dp[k - 1][i1 - 1][i2] + t);
                        //两个数到达nums[i][j]的最后一步一个从左往右走，一个从上往下走
                        dp[k][i1][i2] = Math.max(dp[k][i1][i2],dp[k - 1][i1][i2 - 1] + t);
                        //两个数到达nums[i][j]的最后一步都是从左往右走
                        dp[k][i1][i2] = Math.max(dp[k][i1][i2],dp[k - 1][i1][i2] + t);
                    }
                }
            }
        }
        //结果就为：走了2 * n步的到达点dp[i1][j1](i1 = i2 && j1 = j2)的所能摘取的花生的最大值
        System.out.print(dp[2 * n][n][n]);
    }
}
